package pers.qianyu.month_202011.date_20201120;

import java.util.*;

/**
 * 105. 从前序与中序遍历序列构造二叉树
 * https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 *
 * @author mizzle rain
 * @date 2020-11-20 21:20
 */
public class BuildTree {
    private HashMap<Integer, Integer> inOrderIndexMap = new HashMap<>();
    private int[] preorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0) {
            return null;
        }
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; i++) {
            inOrderIndexMap.put(inorder[i], i);
        }
        return recur(0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode recur(int preLeft, int preRight, int inLeft, int inRight) {
        if (preLeft > preRight || inLeft > inRight) {
            return null;
        }
        int preValue = preorder[preLeft];
        TreeNode node = new TreeNode(preValue);
        Integer index = inOrderIndexMap.get(preValue);
        int leftNum = index - inLeft;
        int rightNum = inRight - index;
        node.left = recur(preLeft + 1, preLeft + leftNum,
                inLeft, index - 1);
        node.right = recur(preLeft + leftNum + 1, preRight,
                index + 1, inRight);
        return node;
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
